package stackAndQueue.q4_sortStackByStack;

import java.util.Stack;

/**
 * Project：algorithm
 * Date：2024/6/10
 * Time：20:53
 * Description：用一个栈实现另一个栈的排序
 * 要求：
 *     1.栈顶到栈底从大到小排序
 *     2.不允许再使用其他集合容器
 *     3.可申请新的变量
 * 解法：
 *     1.排序的栈记为stack，辅助栈记为help，stack弹出的元素记为cur
 *     2.如果cur小于等于help栈顶元素，直接压入help
 *     3.如果cur大于help栈顶元素，将help元素逐一弹出，直到cur小于等于help栈顶元素，再压入
 *
 * @author Cao Jiwen
 * @version 1.0
 */
public class SortStackByStack {

    public static void sortStackByStack(Stack<Integer> stack){
        Stack<Integer> help = new Stack<>();
        while (!stack.isEmpty()){
            int cur = stack.pop();
            while (!help.isEmpty() && help.peek() < cur){
                stack.push(help.pop());
            }
            help.push(cur);
        }
        while (!help.isEmpty()){
            stack.push(help.pop());
        }
    }

    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        stack.push(5);
        stack.push(3);
        stack.push(9);
        stack.push(1);
        sortStackByStack(stack);
        System.out.println(stack.toString());
    }
}
